package main

import (
	"fmt"
	"io"
)

/*
构造回文串
  给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
 */

func main() {
	var s string
	for {
		_, err := fmt.Scan(&s)
		if err == io.EOF {
			break
		}
		// 反转一个字符串
		reverse := func(str string) string {
			// 双指针
			strByte := []byte(str)
			left, right := 0, len(strByte) - 1
			for left < right {
				strByte[left], strByte[right] = strByte[right], strByte[left]
				left ++
				right --
			}
			return string(strByte)
		}
		reverseStr := reverse(s)
		// 寻找最长公共子序列
		max := func(x, y int) int {
			if x > y {
				return x
			}
			return y
		}
		temp := make([][]int, len(s) + 1)
		for i := range temp {
			temp[i] = make([]int, len(reverseStr) + 1)
		}
		for i := 1; i <= len(s); i ++ {
			for j := 1; j <= len(reverseStr); j ++ {
				if s [i - 1] == reverseStr[j - 1] {
					temp[i][j] = temp[i -1][j - 1] + 1
				}else {
					temp[i][j] = max(temp[i - 1][j], temp[i][j - 1])
				}
			}
		}
		fmt.Println(len(s) - temp[len(s)][len(reverseStr)])
	}
}
